package com.lw.leetcode.arr.a;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1646. 获取生成数组中的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/23 11:44
 */
public class GetMaximumGenerated {


    public static void main(String[] args) {
        GetMaximumGenerated test = new GetMaximumGenerated();
        for (int i = 0; i < 101; i++) {
            int a = test.getMaximumGenerated(i);
            int b = test.getMaximumGenerated3(i);
            System.out.println(i + "     " + b);
        }
        System.out.println("000000");
    }

    public int getMaximumGenerated(int n) {
        if (n < 2) {
            return n;
        }
        int max = 0;
        for (int i = 2; i <= n; i++) {
            int a = 1;
            int b = i;
            int c = 0;
            while (b > 1) {
                if ((b & 1) == 0) {
                    a += c;
                } else {
                    c += a;
                }
                b >>= 1;
            }
            max = Math.max(a + c, max);
        }
        return max;
    }

    public int getMaximumGenerated3(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        int max = 0;
        for (int i = 2; i <= n; ++i) {
            int k = nums[i] = (i & 1) == 0 ? nums[i >> 1] : nums[i >> 1] + nums[(i >> 1) + 1];
            if (k > max) max = k;
        }
        return max;
    }

    public int getMaximumGenerated2(int n) {
        if (n == 0) {
            return 0;
        }
        int[] nums = new int[n + 1];
        nums[1] = 1;
        for (int i = 2; i <= n; ++i) {
            nums[i] = nums[i / 2] + i % 2 * nums[i / 2 + 1];
        }
        return Arrays.stream(nums).max().getAsInt();
    }

}
